(a) Field of the Invention
The present invention relates to a method for four-path tree structured vector quantization, and more particularly to a method for four-path tree structured vector quantization, in which dynamic four-path tree structured vector quantization is used instead of conventional dynamic two-path tree structured vector quantization, thereby more efficiently and quickly searching a codebook.
(b) Description of the Related Art
In general, vector quantization has been widely used in transmitting and receiving video data. A transmitting terminal previously stores various pieces of data in a codebook and compares it with the video data, thereby sending a receiving terminal only an address that represents a group where the closest (i.e., the most similar) data is collected. The receiving terminal restores the video data with data of the codebook held in a receiving address, while holding the same codebook. For example, if a codebook vector has a length of 64 bytes, it is compared with video data of 64 bytes and only an address (the length of 1 byte) is sent to the receiving terminal, thereby having a compression ratio of 64:1.
When the transmitting terminal compares all data of the codebook with original data, it is called full search (FS). This method takes much time. In the foregoing example, if the number of codebook is 256, the transmitting terminal has to perform the comparison 256 times and search the codebook having the smallest mean square error (mse) in order to determine one codebook address, thereby transmitting the determined codebook address.
If the video data has a size of 1024×2048, the number of address to be transmitted is 32768(=1024×2048/64) and 256 comparisons (when the number of codebook is 256) have to be performed 32768 times.
To solve such shortcomings, there has been proposed a method of tree structured vector quantization. This method employs a tree-structure search when the data of the codebook is compared with video data.
In a tree-structure as shown in FIG. 1, codebook vectors where the magnitudes of vectors (i.e., the square roots of the sums of squared vector components) are arranged in order are placed at the lowermost nodes in the structure (in FIG. 1), and their upper nodes in the same tree-structure are configured by averaging the vectors of adjacent two nodes. In a vector quantization method for the tree-structure, the path having the smaller mean square error (mse) between the input vector and the uppermost tree structured vector is used to transmit the finally selected lowermost codebook vector address. In the vector quantization method for the tree-structure, the number of calculation time is determined in consideration of the number of branch to be compared. Therefore, the codebook vector can be selected by performing comparison 16 times with respect to 256 vectors, of which the number of calculation time is reduced by 1/16 as compared with the conventional comparisons of 256 times. In FIG. 1, G has 120.92=sqrt(85^2+86^2), and 211=((100−85)^2+(100−86)^2)/2. Further, the vector (89, 93) of C is ((85+94)/2, (86+100)/2).
However, the foregoing dynamic path tree structured vector quantization with two branches has a problem that since it is impossible to get out of an unsuitable path even though another path is more suitable, thereby resulting in increasing an error.
To overcome the foregoing problem, there has been proposed a dynamic path tree structured vector quantization, in which a threshold (thr) between 0 and 1 is set up through [Expression 1], and two paths are all taken into account when it is smaller than the threshold but otherwise only a path having a small mse is considered.T=|mse(B1)−mse(B2)|/(mse(B1)+mse(B2))  [Expression 1]
where, mse(B1) and mse(B2) are an mse of a branch 1 and an mse of a branch 2 from the node, respectively.
Referring to FIG. 2, if thr is set to 0.7 (T<thr), both two paths are considered, but otherwise only the path having the small mse is considered, thereby generating many paths finally.
In FIG. 2, two paths of A-D-I and B-E-K are generated. If the last nodes of two paths are compared with respect to the mse, 26 is smaller than 31 and therefore the path of A-D-I path is selected. The number of calculation time is 510(=256+128+64+32+16+8+4+2) when thr is 1, and 16 when thr is 0.
In addition, concept of block gain vector quantization is introduced. Thus, a picture is divided in accordance with blocks, and their average and standard deviation are calculated. Then, such data undergoes normalization (an average: 0, a standard deviation: 1). The average and standard deviation is separately transferred to the receiving terminal and compensated after the quantization.
However, the conventional two path tree-structured vector quantization has a problem of slowing down the calculation and comparison as picture quality of video data has become higher to high definition (HD) or full HD.